# -*- coding: utf-8 -*-

"""剑指 Offer II 086. 分割回文子字符串
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

示例 2：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 3：
输入：s = "a"
输出：[["a"] 

提示：
1 <= s.length <= 16
s 仅由小写英文字母组成"""


class Solution:
    """指针在字符串种从前往后移动，没到一个位置，判断以该位置为起点有哪些回文字符字串，做不同决策后，指针移动到选择的回文子串下一个位置
    排列组合，用回溯+递归
    对于下回合字符串原材料的选择，可以直接用指针来表示
    可以提前枚举出所有的回文子串，用 {start: [ends...]} 表示，方便回溯的时候直接查表，况且也较容易实现"""
    def partition(self, s: str):
        def enum_palins(s):
            answer = dict()
            s = ','.join(s)
            for i in range(len(s)):
                l, r = i, i
                while True:
                    try:
                        if s[l] != s[r]:
                            break
                        if s[l] != ',' and s[l] == s[r]:
                            if l//2 in answer.keys():
                                answer[l//2].append(r//2)
                            else:
                                answer[l//2] = [r//2]
                        l -= 1
                        r += 1
                    except IndexError:
                        break
            return answer
        palins = enum_palins(s)

        answer, hi = [], len(s)
        def fork(start, group):
            if start == hi:
                answer.append(group)
                return
            
            for end in palins[start]:
                group_new = group.copy()
                group_new.append(s[start:end+1])
                fork(end+1, group_new)
        fork(0, [])
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.partition(s = "google"))
    print(so.partition(s = "aab"))
    print(so.partition(s = "a"))
    print(so.partition(s = "abbab"))
